package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func reorderList(head *ListNode) {
	if head == nil || head.Next == nil {
		return
	}
	// 寻找中点
	n := head
	mid := head
	prev := &ListNode{
		Next: head,
	}
	for n != nil && mid != nil {
		mid = mid.Next
		prev = prev.Next
		n = n.Next
		if n != nil {
			n = n.Next
		}
	}
	prev.Next = nil // 切断前后两个链表
	// 反转后半部分链表
	n = mid
	n1 := n.Next
	for n1 != nil {
		n2 := n1.Next
		n1.Next = n
		n = n1
		n1 = n2
	}
	mid.Next = nil
	tail := n
	// 合并两个链表
	n1 = head
	n2 := tail
	result := &ListNode{}
	n = result
	for n1 != nil && n2 != nil {
		n.Next = n1
		n1 = n1.Next
		n = n.Next
		n.Next = n2
		n = n.Next
		n2 = n2.Next
	}
	if n1 != nil {
		n.Next = n1
	}
	if n2 != nil {
		n.Next = n2
	}
}

func makeList(vals ...int) *ListNode {
	hair := &ListNode{}
	n := hair
	for _, v := range vals {
		n.Next = &ListNode{
			Val: v,
		}
		n = n.Next
	}
	return hair.Next
}

func main() {
	l1 := makeList(1, 2, 3, 4, 5, 6, 7)
	reorderList(l1)
	println(l1)
}
